package code.classic150on2025;

import java.util.*;

public class TheMath {
    // 172. 阶乘后的零
    public int trailingZeroes(int n) {
        int numOfFive = 0;
        for (int i = 1; i <= n; i++) {
            int num = i;
            while (num % 5 == 0) {
                numOfFive++;
                num /= 5;
            }
        }
        return numOfFive;
    }

    // 50. Pow(x, n)
    public double myPow(double x, int n) {
        if (n == 0)
            return 1;
        if (n == 1)
            return x;
        if (n == -1)
            return 1 / x;
        double tempPow = myPow(x, n / 2);
        if (Math.abs(n) % 2 == 1) {
            if (n > 0)
                return tempPow * tempPow * x;
            else
                return tempPow * tempPow * (1 / x);
        } else
            return tempPow * tempPow;
    }

    // 149. 直线上最多的点数
    public int maxPoints(int[][] points) {
        int len = points.length;
        if (len <= 2)
            return len;
        // Point类表示平面中的一个点；Line类表示平面中的一条直线
        Map<Line, Set<Point>> map = new HashMap<>();
        // 找到所有的直线，并把对应的点加入直线
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len; j++) {
                Point p1 = new Point(points[i][0], points[i][1]);
                Point p2 = new Point(points[j][0], points[j][1]);
                Line l = new Line(p1, p2);
                if (!map.containsKey(l))
                    map.put(l, new HashSet<>());
                map.get(l).add(p1);
                map.get(l).add(p2);
            }
        }
        // 遍历所有直线，找点最多的那个
        int max = 0;
        for (Line l : map.keySet()) {
            max = Math.max(max, map.get(l).size());
        }
        return max;
    }

    static class Point {
        int x, y;

        public Point(int a, int b) {
            x = a;
            y = b;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Point)) return false;
            Point p = (Point) obj;
            return p.x == x && p.y == y;
        }
    }

    static class Line {
        int A, B, C;

        public Line(Point p1, Point p2) {
            A = p2.y - p1.y;
            B = p1.x - p2.x;
            C = p2.x * p1.y - p1.x * p2.y;
            int gdc = gdc(Math.abs(A), gdc(Math.abs(B), Math.abs(C)));
            if (gdc != 0) {
                A /= gdc;
                B /= gdc;
                C /= gdc;
            }
            if (A < 0 || (A == 0 && B < 0)) {
                A = -A;
                B = -B;
                C = -C;
            }
        }

        private int gdc(int a, int b) {
            return b == 0 ? a : gdc(b, a % b);
        }

        @Override
        public int hashCode() {
            return Objects.hash(A, B, C);
        }

        @Override
        public boolean equals(Object obj) {
            if (!(obj instanceof Line)) return false;
            Line l = (Line) obj;
            return l.A == A && l.B == B && l.C == C;
        }
    }
}
